package com.Questions.hash;

import java.util.*;

/**
 * 使数组连续的最小操作次数
 */
public class leetcode2009 {
    public int minOperations(int[] nums) {
        // 最后连续的数组最小值为left 则最大值right=left+n-1
        // 原数组nums中 如果有位于[left,right]中的 出现一次进行保留
        // 多次出现 需要对其进行操作 如果不在这个区间 也需要对其进行操作
        // 如果确定left 可以将原数组nums所有不同的数字作为left的候选 值
        // 分别计算n-k然后求出最小值
        int n=nums.length;
        Set<Integer> set=new HashSet<>();
        for(int num:nums){// 去重
            set.add(num);
        }
        List<Integer> sortedUniqueNums=new ArrayList<>(set);
        Collections.sort(sortedUniqueNums);// 排序
        int res=n;
        int j=0;
        for(int i=0;i<sortedUniqueNums.size();++i){// 枚举所有left可能的值
            int left=sortedUniqueNums.get(i);
            int right=left+n-1;// 计算出right的值
            // 不重复 而且在规定的区间范围之内 就是不需要操作的字符的个数
            // 直接使用n减去这个数 就是需要操作的次数
            // 返回枚举中的最小值即可
            while (j<sortedUniqueNums.size()&&sortedUniqueNums.get(j)<=right){// j一定大于等于i
                res=Math.min(res,n-(j-i+1));// j-i+1 为 在不重复的范围内 并且数值在left到right区间之内的数字个数
                j++;
            }
        }
        return res;
    }
}
